package Demo1;

public class Sort {
    // 插入排序
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= 0 ; j--) {
                if (array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    // 希尔排序
    private static void oneshell(int[] array, int gap){
        for (int i = gap; i < array.length; i++){
            int j = i - gap;
            int tmp = array[i];
            for(; j >= 0; j -= gap){
                if (array[j] > tmp){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap /= 2;
            oneshell(array, gap);
        }
    }

    // 选择排序
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int minindex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minindex] > array[j]){
                    minindex = j;
                }
            }

            int tmp = array[i];
            array[i] = array[minindex];
            array[minindex] = tmp;
        }
    }


    // 堆排序
    private static void shiftDown(int[] array, int parent, int len){
        int child = 2 * parent + 1;

        while (child < len){
            if (child + 1 < len && array[child] > array[child + 1]){
                child++;
            }

            if (array[child] < array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }


        }

    }

    private static void createHeap(int[] array){
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }

    public static void heapSort(int[] array){
        createHeap(array);
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag){
                return;
            }
        }
    }

    // 快速
    public static void quickSort(int[] array){
        // write code  here
    }
}


class Main{
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 9, 17, 1, 23};
        Sort.insertSort(array);

        for (int s : array) {
            System.out.print(s + " ");
        }

        System.out.println();

        array = new int[]{2, 3, 9, 17, 1, 23};
        Sort.shellSort(array);

        for (int s : array) {
            System.out.print(s + " ");
        }

        System.out.println();
        array = new int[]{2, 3, 9, 17, 1, 23};
        Sort.selectSort(array);
        for (int s : array){
            System.out.print(s + " ");
        }

/*        System.out.println();
        int[] array = new int[]{2, 3, 9, 17, 1, 23};
        Sort.bubbleSort(array);
        for (int s : array){
            System.out.print(s + " ");
        }*/
    }
}
